package club.babyf.nativeai.demo.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * SubarraySum.
 *
 * @author zhanglei.
 * @date 2025/5/8 16:12.
 * @description 将数组中的数字任意组合求和为k，求最大的可能组合.
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数，子数组是数组中元素的连续非空序列。
 */
public class _11_SubarraySum {

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> preSumCount = new HashMap<>();

        // 初始前缀和为0出现一次
        preSumCount.put(0, 1);
        int currentSum = 0;
        int count = 0;

        for (int num : nums) {
            // 计算当前前缀和
            currentSum += num;
            int target = currentSum - k;

            // 如果存在target对应的前缀和，则累加次数
            count += preSumCount.getOrDefault(target, 0);

            // 更新当前前缀和的出现次数
            preSumCount.put(currentSum, preSumCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        _11_SubarraySum subarraySum = new _11_SubarraySum();
        int[] nums = {1, 2, 3};
        int count = subarraySum.subarraySum(nums, 3);
        System.out.println(count);
    }

}
